//
// Created by chao.li on 2023/12/22.
//

#ifndef SOLUTIONS_SOLUTION023_H
#define SOLUTIONS_SOLUTION023_H
#include "../common.hpp"

class Solution {
    struct SortListNode
    {
        ListNode* node;
        SortListNode* next;

        SortListNode(ListNode* list, SortListNode* n = nullptr):
            node(list),
            next(n)
        {
        }
    };

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int iter = lists.size() - 1;
        while (iter >= 0){
            if(lists[iter] == nullptr){
                lists.erase(lists.begin() + iter);
            }
            iter --;
        }
        if(lists.empty()){
            return nullptr;
        }

        //使用插入排序

        //先把链表们排序
        auto sortHead = new SortListNode(lists.front());
        for (auto iter = lists.begin() + 1;
            iter < lists.end(); ++iter) {
            if((*iter)->val < sortHead->node->val){
                auto newHead = new SortListNode(*iter);
                newHead->next = sortHead;
                sortHead = newHead;
            } else {
                auto pos = sortHead;
                while(pos->next != nullptr){
                    if(pos->next->node->val < (*iter)->val){
                        pos = pos->next;
                    } else{
                        break;
                    }
                }
                pos->next = new SortListNode(*iter, pos->next);
            }
        }

        //根据排序后的链表，归并排序
        ListNode *fhead = nullptr, *tail = nullptr;

        // 遍历排序后的链表
        while(sortHead->next != nullptr){

            if(tail == nullptr){
                fhead = tail = sortHead->node;
            } else{
                tail->next = sortHead->node;
                tail = tail->next;
            }

            //调整sortHead
            auto temp = sortHead;
            if(temp->node->next != nullptr){
                sortHead = new SortListNode(temp->node->next, temp->next);
                delete temp;
            } else{
                //第一个链表空了
                sortHead = sortHead->next;
            }
            tail->next = nullptr;

            // 看看sortHead是否需要后移
            auto pos = sortHead;
            while(pos->next != nullptr){
                if(pos->next->node->val < sortHead->node->val){
                    pos = pos->next;
                } else{
                    break;
                }
            }

            //后移
            if(pos != sortHead){
                auto t = pos->next;
                auto nhead = sortHead->next;
                pos->next = sortHead;
                sortHead->next = t;
                sortHead = nhead;
            }
        }

        //最后一个链表
        if (sortHead != nullptr && sortHead->node != nullptr){
            if(tail == nullptr){
                fhead =  sortHead->node;
            } else{
                tail->next = sortHead->node;
            }
        }

        return fhead;
    }
};

void test(){
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//    vector<ListNode*> lists = {
//            buildList({1, 4, 5}),
//            buildList({1, 3, 4}),
//            buildList({2, 6}),
//    };

    vector<ListNode*> lists = {nullptr, buildList({1}), };

    Solution s;
    auto list = s.mergeKLists(lists);

    printl(list);
}

#endif //SOLUTIONS_SOLUTION023_H
